package dujiu.leetcode.graph;

import java.util.LinkedList;
import java.util.Queue;

public class bfs {
    // 四个方向：上、右、下、左
    private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public void bfs(char[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>(); // 使用队列存储待访问的节点
        queue.offer(new int[]{x, y}); // 起始节点坐标加入队列
        visited[x][y] = true; // 标记为已访问

        while (!queue.isEmpty()) {
            int[] cur = queue.poll(); // 取出队首节点的坐标
            int curX = cur[0];
            int curY = cur[1];

            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];

                // 检查是否越界
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                    continue;
                }

                // 如果未被访问，加入队列并标记
                if (!visited[nextX][nextY]) {
                    queue.offer(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}
